CF685B Kay and Snowflake

这道题应该算是 CSP2019 树的重心\text{CSP2019 树的重心} 的前置知识了吧。可惜之前我并没有做过。

对于一棵以 uu 为根的子树,它的重心只可能在点 uu 或 以点 uu 的重儿子为根的子树中。

那么类比 lca\text{lca} 倍增父亲,树的重心倍增重儿子。

查询时保证倍增时的子树大小不小于原子树大小的一半(重心的定义)。

最后它和它的父节点都可能是重心,随便判一下就可以了。

#include <cstdio>
#include <vector>
using namespace std;

const int MAXN = 300000 , MAXK = 20;
int n , q;
vector< int > Graph[ MAXN + 5 ];

int Fa[ MAXN + 5 ] , Size[ MAXN + 5 ] , Hson[ MAXN + 5 ] , Anc[ MAXN + 5 ][ MAXK + 1 ];
void dfs( int u ) {
    Size[ u ] = 1;
    for( int i = 0 ; i < Graph[ u ].size() ; i ++ ) {
        int v = Graph[ u ][ i ];
        dfs( v ); Size[ u ] += Size[ v ];
        if( Size[ v ] > Size[ Hson[ u ] ] ) Hson[ u ] = v;
    }
    Anc[ u ][ 0 ] = Hson[ u ];
    for( int i = 1 ; i <= MAXK ; i ++ ) Anc[ u ][ i ] = Anc[ Anc[ u ][ i - 1 ] ][ i - 1 ];
}

bool chk( int u , int v ) { //以u为根的子树,v是否为重心
    return max( Size[ Hson[ v ] ] , Size[ u ] - Size[ v ] ) <= Size[ u ] / 2;
}
int Query( int rt ) {
    int u = rt;
    for( int i = MAXK ; i >= 0 ; i -- )
        if( Anc[ u ][ i ] && Size[ Anc[ u ][ i ] ] >= Size[ rt ] / 2 ) u = Anc[ u ][ i ];
    if( chk( rt , u ) ) return u;
    if( chk( rt , Fa[ u ] ) ) return Fa[ u ];
}

int main( ) {
    scanf("%d %d",&n,&q);
    for( int i = 2 ; i <= n ; i ++ ) {
        scanf("%d",&Fa[ i ]);
        Graph[ Fa[ i ] ].push_back( i );
    }
    dfs( 1 );
    for( int i = 1 , rt ; i <= q ; i ++ ) {
        scanf("%d",&rt);
        printf("%d\n", Query( rt ) );   
    }
    return 0;
}